A study of the effectiveness of detailed balance in avoiding convergence in PBIL

摘要

Estimation of distribution algorithms (EDAs) are a class of evolutionary algorithms that use statistical information to guide the exploration of the search space. A prominent problem in EDAs is the loss of variability as the search progresses. This occurs because at each iteration the probabilistic model reinforces the probability of generating the best solutions found in the previous populations. This process may accelerate convergence to local optima. This paper investigates a method to diminish this convergence pressure by applying “detailed balance” to the Population Based Incremental Learning (PBIL) algorithm [4]. Detailed balance is a well-known condition in Markov chains. Basically, it says that, on a flat fitness landscape, the probability of going from a state i to a state j must be the same as the probability of going backwards from state j to state i. This condition slows the rate of convergence of the probability parameters when the landscape is flat. As a result, the algorithm requires more evidence from the fitness function to drive the search to a single point in the search space and maintains variability for longer.